2. Mathematical Foundations

Assistant Prof. Dr. Siwachoat Srisuttiyakorn

Department of Educational Research and Psychology
Faculty of Education Chulalongkorn University

2025-01-18

Outline

  • Basic Concepts

  • Connectivity and Structure of Graphs

  • Matrices in Network Analysis

Basic Concepts

  • Graphs

  • Directed and Undirected Graphs

  • Social Relations and Implications

  • Multirelational Networks

Graphs

ในทางคณิตศาสตร์ \(G(V,E)\) หมายถึงกราฟที่เป็นโครงสร้างสำหรับแสดงความสัมพันธ์หรือการเชื่อมโยงกันระหว่าง จุดยอดหรือโหนด (vertices หรือ nodes) และ เส้นเชื่อม (edges หรือ links) โดยที่ \(V\) คือเซตของจุดยอด (vertices) หรือ โหนด (nodes) และ \(E\) คือเซตของเส้นเชื่อม (edges or links or line) เช่น

  • \(V(G) = \{1,2,3,...,10\}\)

  • \(E(G) = \{(1,6),(1,8),(4,7),(7,4)... \}\)

adjacent node : โหนดที่เชื่อมต่อกันโดยตรงด้วยเส้นเชื่อมจะเรียกว่า adjacent node

incident : หมายถึงความสัมพันธ์ระหว่าง จุดยอด (vertices) และ เส้นเชื่อม (edges) ในกราฟ กล่าวคือถ้าเส้นเชื่อม \(e\) เชื่อมกับจุดยอด \(u\) และ \(v\) ในกราฟ จะเรียกว่าเส้นเชื่อมนั้น incident กับจุดยอด \(u\) และ \(v\)

degree : หมายถึงจำนวนเส้นเชื่อมที่เชื่อมกับจุดยอด

Directed vs Undirected Graphs 1

กราฟอาจจำแนกได้เป็น 2 ประเภทหลัก ได้แก่ กราฟแบบมีทิศทาง และแบบไม่มีทิศทาง ทั้งสองใช้แทนเครือข่ายที่มีลักษณะแตกต่างกัน

Directed vs Undirected Graphs 2


  • ถูกใช้แทนเครือข่ายที่ความสัมพันธ์มีลักษณะของทิศทางแบบเป็นเหตุเป็นผล เช่น

    • เป็นผู้ปกครองของ…

    • เป็นที่ปรึกษาของ…

  • ความสัมพันธ์แบบมีทิศทางสามารถมีลักษณะเป็นแบบย้อนกลับ (reciprocated ties ) ซึ่งเป็นไปได้ในเครือข่ายที่โหนดมีลักษณะของการปรึกษาหรือช่วยเหลือซึ่งกันและกัน

Directed vs Undirected Graphs 3


  • ใช้แทนเครือข่ายของความสัมพันธ์ที่ไม่มีทิศทาง เช่น

    • การพบเจอกัน

    • การแต่งงานกัน

    • การเป็นเพื่อนกัน รู้จักกัน

Social Relations and Implications

  • ความสัมพันธ์ทางสังคมแต่ละประเภทจะมีโครงสร้าง ความหมาย และผลกระทบที่แตกต่างกันต่อจุดยอดที่เกี่ยวข้อง เช่น

    • ความสัมพันธ์ในเครือข่ายมิตรภาพ จุดยอดที่มี degree จำนวนมากจะหมายถึงความนิยม

    • ความสัมพันธ์ในเครือข่ายการนินทา

    • ความสัมพันธ์ในเครือข่ายความเกลียดชังกัน

  • ผู้วิเคราะห์มักออกแบบ ให้ทุกเส้นเชื่อมในกราฟเป็นความสัมพันธ์แบบเดียวกัน เช่น

    • \(G(V,E)\) เป็นกราฟความสัมพันธ์แบบเพื่อนสนิทในชั้นเรียน

    • \(H(V,A)\) เป็นกราฟความสัมพันธ์ให้คำปรึกษาระหว่างเพื่อน

Multirelational/Multiplex Networks 1

  • เครือข่ายที่จุดยอดชุดเดียวกันมีความสัมพันธ์เกิดขึ้นได้หลายประเภท เรียกว่า multirelational หรือ multiplex networks

  • Isolates คือจุดยอดที่ไม่มีเส้นเชื่อม หรือ degree = 0

  • Pendants คือจุดยอดที่มี degree = 1


Multirelational/Multiplex Networks 2

ลองพิจารณา indegree ของ w1 และ w6 ในเครือข่ายทั้งสอง ความหมายที่ได้แตกต่างกันอย่างไร

Connectivity and Structure of Graphs

  • Paths, Trials, and Walks

  • Geodesic Distances

  • Components

  • Bridges and Cutpoints

  • Cohesion

Paths 1

วิถี (paths) หมายถึงลำดับของจุดยอดที่เชื่อมต่อกันด้วยเส้นเชื่อม (อาจเรียกว่าเป็นลำดับของ adjacent nodes) ที่ไม่มีการใช้เส้นเชื่อมหรือจุดยอดซ้ำ

  • ลองพิจารณา w1 กับ w7 ด้านล่าง ความสัมพันธ์ของโหนดทั้งสองเป็นอย่างไร?

Paths 2

วิถี (paths) หมายถึงลำดับของจุดยอดที่เชื่อมต่อกันด้วยเส้นเชื่อม (อาจเรียกว่าเป็นลำดับของ adjacent nodes) ที่ไม่มีการใช้เส้นเชื่อมหรือจุดยอดซ้ำ

  • ลองพิจารณา w1 กับ w7 ด้านล่าง ความสัมพันธ์ของโหนดทั้งสองเป็นอย่างไร?

  • w1-s1-w3-w4-s1-w7 เป็น path หรือไม่?

Paths 3

วิถี (paths) หมายถึงลำดับของจุดยอดที่เชื่อมต่อกันด้วยเส้นเชื่อม (อาจเรียกว่าเป็นลำดับของ adjacent nodes) ที่ไม่มีการใช้เส้นเชื่อมหรือจุดยอดซ้ำ

  • ลองพิจารณา w1 กับ w7 ด้านล่าง ความสัมพันธ์ของโหนดทั้งสองเป็นอย่างไร?

  • w1-s1-w3-w4-s1-w7 เป็น path หรือไม่?

  • s4-w9-w8-w7 เป็น path หรือไม่?

Paths 4

คุณสมบัติของ Paths

  1. จุดเริ่มต้นและสิ้นสุด
  • Open Path: จุดเริ่มต้นและสิ้นสุดต่างกัน

  • Closed Path: จุดเริ่มต้นและสิ้นสุดเหมือนกัน

  1. ไม่มีการใช้จุดยอดและเส้นเชื่อมซ้ำ ยกเว้นกรณี closed path

  2. สำหรับเครือข่ายที่มีทิศทาง วิถีของการเดินจะต้องเป็นไปตามทิศทางของเส้นเชื่อมเท่านั้น

  3. ความยาวของวิถี (path length) = จำนวนเส้นเชื่อมในวิถีนั้น

Paths 5

รอยเดิน (trails) หมายถึงลำดับของ adjacent nodes ที่ใช้จุดยอดซ้ำได้ โดยที่เส้นเชื่อมแต่จะเส้นจะถูกใช้ได้เพียงครั้งเดียว (ไม่มีการใช้เส้นเชื่อมซ้ำ)

  • w1-s1-w3-w4-s1-w7 เป็น trail หรือไม่

Trials 1

รอยเดิน (trails) หมายถึงลำดับของ adjacent nodes ที่ใช้จุดยอดซ้ำได้ โดยที่เส้นเชื่อมแต่จะเส้นจะถูกใช้ได้เพียงครั้งเดียว (ไม่มีการใช้เส้นเชื่อมซ้ำ)

  • w1-s1-w3-w4-s1-w7 เป็น trail หรือไม่

Trials 2

รอยเดิน (trails) หมายถึงลำดับของ adjacent nodes ที่ใช้จุดยอดซ้ำได้ โดยที่เส้นเชื่อมแต่จะเส้นจะถูกใช้ได้เพียงครั้งเดียว (ไม่มีการใช้เส้นเชื่อมซ้ำ)

  • w1-s1-w3-w4-s1-w7 เป็น trail หรือไม่

  • w8-w7-w9-w8-w7 เป็น trail หรือไม่

Trials 3

รอยเดิน (trails) หมายถึงลำดับของ adjacent nodes ที่ใช้จุดยอดซ้ำได้ โดยที่เส้นเชื่อมแต่จะเส้นจะถูกใช้ได้เพียงครั้งเดียว (ไม่มีการใช้เส้นเชื่อมซ้ำ)

  • w1-s1-w3-w4-s1-w7 เป็น trail หรือไม่

  • w8-w7-w9-w8-w7 เป็น trail หรือไม่


คุณสมบัติของ Trails

  1. ใช้จุดยอดซ้ำได้

  2. ไม่มีการใช้เส้นเชื่อมซ้ำ

  3. มีทั้ง open และ closed trails

Walks

แนวเดิน (walks) หมายถึงลำดับของ adjacent nodes ที่ไม่มีการจำกัดเงื่อนไขเฉพาะ

คุณสมบัติของ Walks

  1. ใช้จุดยอดและเส้นเชื่อมซ้ำได้

  2. มีทั้ง open walks และ closed walks


  • w8-w7-w9-w8-w7 เป็น walk หรือไม่

Paths, Trails, and Walks 1

แนวคิดของ paths, trails และ walks สามารถนำมาใช้แทนปรากฏการณ์เกี่ยวกับความสัมพันธ์ในเครือข่ายที่ต้องการอธิบายได้ เช่น

  • การแพร่กระจายข่าว

  • การแพร่กระจายไวรัส

  • การโต้ตอบกระทู้ใน discussion board

คุณสมบัติ Paths Trails Walks
การใช้จุดยอด ห้ามซ้ำ อนุญาตให้จุดยอดซ้ำได้ อนุญาตให้จุดยอดซ้ำได้
การใช้เส้นเชื่อม ห้ามซ้ำ ห้ามซ้ำ อนุญาตให้เส้นเชื่อมซ้ำได้

Paths, Trails, and Walks 2

แนวคิดของ paths, trails และ walks สามารถนำมาใช้แทนปรากฏการณ์เกี่ยวกับความสัมพันธ์ในเครือข่ายที่ต้องการอธิบายได้ เช่น

การแพร่กระจายข่าว (เชิงนินทา) : ลองพิจารณาลำดับของ adjacent nodes ต่อไปนี้

\[ W1 \rightarrow S1 \rightarrow W3 \rightarrow W4 \rightarrow S1 \rightarrow W7 \]

  • ลำดับข้างต้นเป็นลำดับประเภทไหน?

  • เป็นไปได้หรือไม่ที่การเดินทางของข่าวจะเดินทางในลำดับข้างต้น ?

Paths, Trails, and Walks 3

การแพร่ระบาดของเชื้อไวรัส ที่แพร่กระจายผ่านการมีปฏิสัมพันธ์

  • Walks

  • Trails

  • Paths

Paths, Trails, and Walks 4

การโต้ตอบกระทู้ใน discussion board

  • Walks

  • Trails

  • Paths

Geodesics

Geodesic distance: หรือ distance หมายถึง ระยะทางสั้นที่สุดของแนวเดิน (walk) ที่วัดจากจำนวนเส้นเชื่อมที่ใช้เชื่อมต่อจุดเริ่มต้นและจุดสิ้นสุดของแนวเดินนั้น

พิจารณา path ต่อไปนี้

  • w3-w4-s1

  • w3-w1-s1

Note: จะเห็นว่า geodesic distance ใช้บ่งชี้หรือสะท้อนการเดินทางของสิ่ง ๆ ใดในเครือข่ายว่าภายใต้สถานการณ์ที่ดีที่สุด การเดินทางของสิ่ง ๆ นั้นอาจจะต้องใช้เวลา

Components 1

ส่วนประกอบ (components) หมายถึงกลุ่มของโหนดที่ใหญ่ที่สุด (maximal set) ที่สามารถเชื่อมถึงกันได้ด้วย path อย่างน้อยหนึ่ง path

  • มี path จาก Holly ไปยัง Brazey หรือไม่?

  • \(\{Bill, Don, Michael\}\) ถือเป็น Component หรือไม่ เพราะ?

  • \(\{Gery, Russ\}\) เป็น component หรือไม่?

  • \(\{Carol \}\) เป็น component หรือไม่

  • Component ที่ใหญ่ที่สุดมีใครบ้าง?

Components 2

ส่วนประกอบ (components) หมายถึงกลุ่มของโหนดที่ใหญ่ที่สุด (maximal set) ที่สามารถเชื่อมถึงกันได้ด้วย path อย่างน้อยหนึ่ง path

Component อาจจำแนกเป็น 2 ประเภท

  • Weak Connected Component: กลุ่มของโหนดที่ใหญ่ที่สุดที่สามารถเชื่อมถึงกันได้ผ่าน path โดยไม่สนใจทิศทางของเส้นเชื่อม

  • Strong Connected Component: กลุ่มของโหนดที่เชื่อมกันด้วย path ที่สนใจทิศทาง

Bridges & Cutpoints 1

Bridge หมายถึง เส้นเชื่อม \(e\) ในกราฟ \(G\) ที่เมื่อลบเส้นเชื่อมดังกล่าวจากกราฟจะเพิ่มจำนวน components ในกราฟ

Cutpoints หมายถึง โหนดในกราฟที่เมื่อถูกลบออกไปพร้อมกับเส้นเชื่อมทั้งหมดที่เกี่ยวข้อง จะทำให้เพิ่มจำนวน component ในกราฟ

Bridges & Cutpoints 2

  • ระบุเส้นเชื่อมที่เป็น Bridges

  • ระบุโหนดที่เป็น Cutpoints

Cohesion 1

ระดับของการเชื่อมต่อระหว่างโหนดในกราฟ หรือ ความใกล้ชิดทางโครงสร้างระหว่างกลุ่มของโหนด โดยทั่วไปจะสะท้อนถึงความแน่นแฟ้นของความสัมพันธ์ในเครือข่าย

  • Cohesion ระหว่างสองโหนด (dyadic cohesion)

  • Cohesion ภายในกลุ่มของโหนด (group cohesion)

ตัวชี้วัด cohesion มีหลายลักษณะ เช่น

  • Adjacency: การมีเส้นเชื่อมระหว่างโหนดสองโหนด

  • Geodesic Distance: ระยะทางสั้นที่สุดระหว่างโหนดสองโหนดในกราฟ

    • ระยะทางสั้นหมายถึงความใกล้ชิดที่เพิ่มขึ้น

    • มักรายงานเป็นส่วนกลับของระยะทาง \(cohesion = 1/d\) แต่บางกรณีอาจเกิดปัญหา?

  • Component: โหนดที่อยู่ภายใต้ component เดียวกันถือว่ามี cohesion ต่อกัน

  • Density: สัดส่วนจำนวนเส้นเชื่อมภายใต้กราฟเทียบกับจำนวนเส้นเชื่อมทั้งหมดที่เป็นไปได้

Cohesion 2: Adjacency

Matrices in Social Network analysis

  • Adjacency and Distance matrices

  • Ways and Modes

  • Matrix products

Adjacency Matrices

อีกวิธีการหนึ่งในการทำความเข้าใจเครือข่ายในเชิงคณิตศาสตร์ คือการนิยามเครือข่ายด้วย adjacency matrix

Adjacency matrix: แถวและคอลัมน์ของเมทริกซ์ใช้แทนโหนด และค่าภายใน cell ตำแหน่ง \(ij\) ใช้แทนสถานะการเชื่อมต่อระหว่างโหนด \(i\) กับ \(j\)

   I1 I3 W1 W2 W3 W4 W5 W6 W7 W8 W9 S1 S2 S4
I1  0  0  0  0  1  0  0  0  0  0  0  0  0  0
I3  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W1  0  0  0  0  1  1  0  0  0  0  0  1  0  0
W2  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W3  1  0  1  0  0  1  0  0  0  0  0  1  0  0
W4  0  0  1  0  1  0  0  0  0  0  0  1  0  0
W5  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W6  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W7  0  0  0  0  0  0  0  0  0  1  1  1  0  0
W8  0  0  0  0  0  0  0  0  1  0  1  0  0  1
W9  0  0  0  0  0  0  0  0  1  1  0  0  0  1
S1  0  0  1  0  1  1  0  0  1  0  0  0  0  0
S2  0  0  0  0  0  0  0  0  0  0  0  0  0  0
S4  0  0  0  0  0  0  0  0  0  1  1  0  0  0

Distance Matrix

นอกจากการเก็บค่าเป็น 1, 0 ที่แสดงการเชื่อมโยงระหว่างโหนด เรายังสามารถใช้เมทริกซ์เพื่อเก็บลักษณะการเชื่อมโยงอื่น ๆ เช่น geodesic distance ดังตัวอย่างด้านล่าง

    I1  I3  W1  W2  W3  W4  W5  W6  W7  W8  W9  S1  S2  S4
I1   0 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf
I3 Inf   0 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf
W1 Inf Inf   0 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf
W2 Inf Inf Inf   0 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf
W3 Inf Inf Inf Inf   0 Inf Inf Inf Inf Inf Inf Inf Inf Inf
W4 Inf Inf Inf Inf Inf   0   1   1   1   2   1   2 Inf   2
W5 Inf Inf Inf Inf Inf   1   0   1   2   2   2   1 Inf   2
W6 Inf Inf Inf Inf Inf   1   1   0   1   1   1   1 Inf   1
W7 Inf Inf Inf Inf Inf   1   2   1   0   1   1   2 Inf   1
W8 Inf Inf Inf Inf Inf   2   2   1   1   0   1   1 Inf   1
W9 Inf Inf Inf Inf Inf   1   2   1   1   1   0   1 Inf   2
S1 Inf Inf Inf Inf Inf   2   1   1   2   1   1   0 Inf   1
S2 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf   0 Inf
S4 Inf Inf Inf Inf Inf   2   2   1   1   1   2   1 Inf   0

Ways and Modes 1

  • Ways คือจำนวนมิติ (dimension) ของเมทริกซ์

  • Modes คือประเภทของหน่วยข้อมูล (type of entities) ที่แถวและคอลัมน์ และมิติที่สูงกว่านั้นของเมทริกซ์ (หรือ array) ใช้แทน

ตัวอย่างด้านล่างแสดง two-way, one-mode matrix

   I1 I3 W1 W2 W3 W4 W5 W6 W7 W8 W9 S1 S2 S4
I1  0  0  0  0  1  0  0  0  0  0  0  0  0  0
I3  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W1  0  0  0  0  1  1  0  0  0  0  0  1  0  0
W2  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W3  1  0  1  0  0  1  0  0  0  0  0  1  0  0
W4  0  0  1  0  1  0  0  0  0  0  0  1  0  0
W5  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W6  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W7  0  0  0  0  0  0  0  0  0  1  1  1  0  0
W8  0  0  0  0  0  0  0  0  1  0  1  0  0  1
W9  0  0  0  0  0  0  0  0  1  1  0  0  0  1
S1  0  0  1  0  1  1  0  0  1  0  0  0  0  0
S2  0  0  0  0  0  0  0  0  0  0  0  0  0  0
S4  0  0  0  0  0  0  0  0  0  1  1  0  0  0
[1] 14 14

Ways and Modes 2

ตัวอย่างด้านล่างแสดง two-way, two-mode matrix

  • แถว คือชื่อของผู้หญิงจำนวน 18 คน

  • คอลัมน์ คือกิจกรรมที่ผู้หญิงเข้าร่วม

          E01 E02 E03 E04 E05 E06 E07 E08 E09 E10 E11 E12 E13 E14
EVELYN      1   1   1   1   1   1   0   1   1   0   0   0   0   0
LAURA       1   1   1   0   1   1   1   1   0   0   0   0   0   0
THERESA     0   1   1   1   1   1   1   1   1   0   0   0   0   0
BRENDA      1   0   1   1   1   1   1   1   0   0   0   0   0   0
CHARLOTTE   0   0   1   1   1   0   1   0   0   0   0   0   0   0
FRANCES     0   0   1   0   1   1   0   1   0   0   0   0   0   0
ELEANOR     0   0   0   0   1   1   1   1   0   0   0   0   0   0
PEARL       0   0   0   0   0   1   0   1   1   0   0   0   0   0
RUTH        0   0   0   0   1   0   1   1   1   0   0   0   0   0
VERNE       0   0   0   0   0   0   1   1   1   0   0   1   0   0
MYRNA       0   0   0   0   0   0   0   1   1   1   0   1   0   0
KATHERINE   0   0   0   0   0   0   0   1   1   1   0   1   1   1
SYLVIA      0   0   0   0   0   0   1   1   1   1   0   1   1   1
NORA        0   0   0   0   0   1   1   0   1   1   1   1   1   1
HELEN       0   0   0   0   0   0   1   1   0   1   1   1   0   0
DOROTHY     0   0   0   0   0   0   0   1   1   0   0   0   0   0
OLIVIA      0   0   0   0   0   0   0   0   1   0   1   0   0   0
FLORA       0   0   0   0   0   0   0   0   1   0   1   0   0   0
[1] 18 14

Ways and Modes 3

สมมติว่าเรามีเครือข่ายความสัมพันธ์ระหว่างบุคคลในกลุ่มเพื่อน 4 คน: A, B, C, และ D เราสนใจว่าใครรู้จักใคร (Friendship Network)

ข้อมูล

  • A รู้จัก B และ C

  • B รู้จัก A และ D

  • C รู้จัก A

  • D รู้จัก B

adjacency matrix ในกรณีนี้จะมีลักษณะคือ แถวเป็นผู้ส่งความสัมพันธ์ ส่วนคอลัมน์เป็นผู้รับความสัมพันธ์

  A B C D
A 0 1 1 0
B 1 0 0 1
C 1 0 0 0
D 0 1 0 0

เมทริกซ์ข้างต้นเรียกว่า ?

Matrix products 1

กำหนดให้ \(A\) และ \(B\) เป็นเมทริกซ์ที่สามารถคูณกันได้ ผลคูณระหว่างทั้งสองเมทริกซ์ \(C = AB\) สามารถคำนวณได้ตามนิยามดังนี้

\[ c_{ij} = \sum_{k} a_{ik}b_{kj} \]

ผลลัพธ์ที่ได้คือผลรวมเชิงเส้นระหว่างสมาชิกในแถวของ A กับสมาชิกในคอลัมน์ของ B

https://charchithowitzer.medium.com/matrix-multiplication-why-is-it-a-big-deal-cc8ef7490008

Matrix products 2

  • ช่วยทำความเข้าใจความสัมพันธ์ที่ลึกซึ้งขึ้น

  • นับจำนวนเส้นทาง

  • คำนวณค่าความสำคัญของโหนด

  • ตรวจจับกลุ่มย่อยภายในเครือข่าย

Matrix products 3

สมมติว่าเรามีเมทริกซ์ \(F\) และ \(C\) คือเมทริกซ์เครือข่ายความเป็นเพื่อน และคู่ขัดแย้ง ผลคูณระหว่างเมทริกซ์ทั้งสอง \(F \times C\) จะให้เมทริกซ์ที่แสดงจำนวนเพื่อนของ \(i\) ที่เป็นคู่ขัดแย้งของ \(j\) (คู่ขัดแย้งในกลุ่มเพื่อน)

\(F\) = เมทริกซ์ความเป็นเพื่อน

\(F_{ij} = 1\) หมายถึง โหนด \(i\) และ \(j\) เป็นเพื่อนกัน

\(F_{ij} = 0\) หมายถึง โหนด \(i\) และ \(j\) ไม่มีความสัมพันธ์กันแบบเพื่อน

   I1 I3 W1 W2 W3 W4 W5 W6 W7 W8 W9 S1 S2 S4
I1  0  0  0  0  1  0  0  0  0  0  0  0  0  0
I3  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W1  0  0  0  0  1  1  0  0  0  0  0  1  0  0
W2  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W3  1  0  1  0  0  1  0  0  0  0  0  1  0  0
W4  0  0  1  0  1  0  0  0  0  0  0  1  0  0
W5  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W6  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W7  0  0  0  0  0  0  0  0  0  1  1  1  0  0
W8  0  0  0  0  0  0  0  0  1  0  1  0  0  1
W9  0  0  0  0  0  0  0  0  1  1  0  0  0  1
S1  0  0  1  0  1  1  0  0  1  0  0  0  0  0
S2  0  0  0  0  0  0  0  0  0  0  0  0  0  0
S4  0  0  0  0  0  0  0  0  0  1  1  0  0  0

\(C\) = เมทริกซ์ความเป็นคู่ขัดแย้ง

\(C_{ij} = 1\) หมายถึง โหนด \(i\) และ \(j\) เป็นคู่ขัดแย้ง

\(C_{ij} = 0\) หมายถึง โหนด \(i\) และ \(j\) ไม่มีความสัมพันธ์แบบคู่ขัดแย้ง

   I1 I3 W1 W2 W3 W4 W5 W6 W7 W8 W9 S1 S2 S4
I1  0  0  0  0  0  0  0  0  0  0  0  0  0  0
I3  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W1  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W2  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W3  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W4  0  0  0  0  0  0  1  1  1  0  1  0  0  0
W5  0  0  0  0  0  1  0  1  0  0  0  1  0  0
W6  0  0  0  0  0  1  1  0  1  1  1  1  0  1
W7  0  0  0  0  0  1  0  1  0  1  1  0  0  1
W8  0  0  0  0  0  0  0  1  1  0  1  1  0  1
W9  0  0  0  0  0  1  0  1  1  1  0  1  0  0
S1  0  0  0  0  0  0  1  1  0  1  1  0  0  1
S2  0  0  0  0  0  0  0  0  0  0  0  0  0  0
S4  0  0  0  0  0  0  0  1  1  1  0  1  0  0

Matrix products 4

Matrix products 5

\(F \times C\) = จำนวนเพื่อนของ \(i\) ที่เป็นคู่ขัดแย้งกับ \(j\)

  • จำนวนเพื่อนของ S1 ที่เป็นคู่ขัดแย้งกับ W7

  • จำนวนเพื่อนของ W1 ที่เป็นคู่ขัดแย้งกับ W6

   I1 I3 W1 W2 W3 W4 W5 W6 W7 W8 W9 S1 S2 S4
I1  0  0  0  0  0  0  0  0  0  0  0  0  0  0
I3  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W1  0  0  0  0  0  0  2  2  1  1  2  0  0  1
W2  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W3  0  0  0  0  0  0  2  2  1  1  2  0  0  1
W4  0  0  0  0  0  0  1  1  0  1  1  0  0  1
W5  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W6  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W7  0  0  0  0  0  1  1  3  2  2  2  2  0  2
W8  0  0  0  0  0  2  0  3  2  3  1  2  0  1
W9  0  0  0  0  0  1  0  3  2  2  2  2  0  2
S1  0  0  0  0  0  1  1  2  1  1  2  0  0  1
S2  0  0  0  0  0  0  0  0  0  0  0  0  0  0
S4  0  0  0  0  0  1  0  2  2  1  1  2  0  1

Matrix products 6

  • เมทริกซ์ไม่มีสมบัติสลับที่การคูณ ดังนั้น \(FC\) ไม่จำเป็นต้องเท่ากับ \(CF\)

  • ตัวอย่างด้านล่างแสดงผลคูณของ \(CF\) แปลความหมายได้อย่างไร

   I1 I3 W1 W2 W3 W4 W5 W6 W7 W8 W9 S1 S2 S4
I1  0  0  0  0  0  0  0  0  0  0  0  0  0  0
I3  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W1  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W2  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W3  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W4  0  0  0  0  0  0  0  0  1  2  1  1  0  1
W5  0  0  2  0  2  1  0  0  1  0  0  1  0  0
W6  0  0  2  0  2  1  0  0  3  3  3  2  0  2
W7  0  0  1  0  1  0  0  0  2  2  2  1  0  2
W8  0  0  1  0  1  1  0  0  2  3  2  1  0  1
W9  0  0  2  0  2  1  0  0  2  1  2  2  0  1
S1  0  0  0  0  0  0  0  0  2  2  2  0  0  2
S2  0  0  0  0  0  0  0  0  0  0  0  0  0  0
S4  0  0  1  0  1  1  0  0  2  1  2  1  0  1
  • ถ้า \(F\) เป็นความสัมพันธ์แบบเพื่อน และ \(B\) เป็นความสัมพันธ์แบบเป็นหัวหน้าของ แล้ว \(FB\) แปลว่า?

  • \(BF\) แปลว่า

Matrix products 7

  • ตัวอย่างด้านล่างแสดงผลคูณ \(FF\) แปลว่า

  • มองได้มั้ยว่าเป็นจำนวนการเดิน (walks) ที่มีความยาวเท่ากับ 2 หน่วย จากโหนด \(i\) ไปยัง \(j\)

   I1 I3 W1 W2 W3 W4 W5 W6 W7 W8 W9 S1 S2 S4
I1  1  0  1  0  0  1  0  0  0  0  0  1  0  0
I3  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W1  1  0  3  0  2  2  0  0  1  0  0  2  0  0
W2  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W3  0  0  2  0  4  2  0  0  1  0  0  2  0  0
W4  1  0  2  0  2  3  0  0  1  0  0  2  0  0
W5  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W6  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W7  0  0  1  0  1  1  0  0  3  1  1  0  0  2
W8  0  0  0  0  0  0  0  0  1  3  2  1  0  1
W9  0  0  0  0  0  0  0  0  1  2  3  1  0  1
S1  1  0  2  0  2  2  0  0  0  1  1  4  0  0
S2  0  0  0  0  0  0  0  0  0  0  0  0  0  0
S4  0  0  0  0  0  0  0  0  2  1  1  0  0  2

Matrix products 8

  • ตัวอย่างด้านล่างแสดงผลคูณ \(F^3\) แปลว่า
   I1 I3 W1 W2 W3 W4 W5 W6 W7 W8 W9 S1 S2 S4
I1  0  0  2  0  4  2  0  0  1  0  0  2  0  0
I3  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W1  2  0  6  0  8  7  0  0  2  1  1  8  0  0
W2  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W3  4  0  8  0  6  8  0  0  2  1  1  9  0  0
W4  2  0  7  0  8  6  0  0  2  1  1  8  0  0
W5  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W6  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W7  1  0  2  0  2  2  0  0  2  6  6  6  0  2
W8  0  0  1  0  1  1  0  0  6  4  5  1  0  5
W9  0  0  1  0  1  1  0  0  6  5  4  1  0  5
S1  2  0  8  0  9  8  0  0  6  1  1  6  0  2
S2  0  0  0  0  0  0  0  0  0  0  0  0  0  0
S4  0  0  0  0  0  0  0  0  2  5  5  2  0  2

Matrix products 9

\(F^k\) = จำนวนการเดินที่มีความยาว \(k\) จากโหนด \(i\) ไป \(j\)

  • ผลลัพธ์นี้ทำให้ผู้วิเคราะห์สามารถทำความเข้าใจได้ว่าการเชื่อมโยงของแต่ละโหนดมีการเชื่อมโยงกับโหนดที่อยู่ไกลออกไปมากแค่ไหนภายในเครือข่าย

  • Concept นี้นำไปสู่การสร้างตัวชี้วัด Beta Centrality

Matrix products 10

\(A \times A^T\) หมายถึงจำนวนโหนดที่มีความสัมพันธ์หรือเชื่อมโยงกับทั้ง \(j\) และ \(j\)

  • \(F \times F^T\) หมายถึงจำนวนเพื่อนร่วมกันระหว่าง \(i\) กับ \(j\)

  • \(C \times C^T\) หมายถึงจำนวนคู่ขัดแย้งร่วมกันระหว่าง \(i\) กับ \(j\)

ตัวอย่างด้านล่างแสดงผลลัพธ์จาก \(F \times F^T\)

   I1 I3 W1 W2 W3 W4 W5 W6 W7 W8 W9 S1 S2 S4
I1  1  0  1  0  0  1  0  0  0  0  0  1  0  0
I3  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W1  1  0  3  0  2  2  0  0  1  0  0  2  0  0
W2  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W3  0  0  2  0  4  2  0  0  1  0  0  2  0  0
W4  1  0  2  0  2  3  0  0  1  0  0  2  0  0
W5  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W6  0  0  0  0  0  0  0  0  0  0  0  0  0  0
W7  0  0  1  0  1  1  0  0  3  1  1  0  0  2
W8  0  0  0  0  0  0  0  0  1  3  2  1  0  1
W9  0  0  0  0  0  0  0  0  1  2  3  1  0  1
S1  1  0  2  0  2  2  0  0  0  1  1  4  0  0
S2  0  0  0  0  0  0  0  0  0  0  0  0  0  0
S4  0  0  0  0  0  0  0  0  2  1  1  0  0  2